{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{a: {}, b: {}, c: {}, d: {}, e: {}}\n",
      "{a: {b: (a,b), c: (a,c), d: (a,d), e: (a,e)}, b: {a: (a,b), c: (b,c)}, c: {a: (a,c), b: (b,c), d: (c,d)}, d: {a: (a,d), c: (c,d), e: (d,e)}, e: {a: (a,e), d: (d,e)}}\n",
      "5\n",
      "7\n",
      "[a, b, c, d, e]\n",
      "[(a,c), (a,b), (c,d), (b,c), (a,d), (a,e), (d,e)]\n"
     ]
    }
   ],
   "source": [
    "class Graph(object):\n",
    "    class Vertex(object):\n",
    "        __slots__='_elem'\n",
    "        def __init__(self,x):\n",
    "            self._elem = x\n",
    "        #加上@property，方法变成属性，按照属性的方式调用，否则按照方法调用加()\n",
    "        def elem(self):\n",
    "            return self._elem\n",
    "        def __hash__(self):\n",
    "            #hash值，唯一确定顶点\n",
    "            return hash(id(self))\n",
    "        def __repr__(self):\n",
    "            return str(self._elem)\n",
    "    \n",
    "    class Edge(object):\n",
    "        __slots__='_src','_des','_elem'\n",
    "        \n",
    "        def __init__(self, u, v, x):\n",
    "            self._src = u\n",
    "            self._des = v\n",
    "            self._elem = x\n",
    "        def endpoints(self):\n",
    "            #取两个端点\n",
    "            return (self._src,self._des)\n",
    "        def opposite(self,v):\n",
    "            #已知一个端点和所在边，返回另一个端点\n",
    "            if not isinstance(v,Graph.Vertex):\n",
    "                raise TypeError('v must be a Vertex')\n",
    "            return self._des if v is self._src else self._src\n",
    "        def elem(self):\n",
    "            return self._elem\n",
    "        def __hash__(self):\n",
    "            return hash((self._src,self._des))\n",
    "        def __repr__(self):\n",
    "            return f'({self._src},{self._des})'#,{self._elem})'\n",
    "    \n",
    "    def __init__(self,directed=False):\n",
    "        self._outgoing={}#出边集合\n",
    "        self._incoming={} if directed else self._outgoing#入边集合\n",
    "    def _validate_vertex(self,v):\n",
    "        #检验是不是顶点\n",
    "        if not isinstance(v,self.Vertex):\n",
    "            raise TypeError('Vertex expected')\n",
    "        #检验顶点在不在图中，检验字典中的键，不能检验值，值是可变的\n",
    "        if v not in self._outgoing:\n",
    "            raise ValueError('Vertex does not belong to this graph.')\n",
    "    def is_directed(self):\n",
    "        return self._incoming is not self._outgoing\n",
    "    @property\n",
    "    def n_vertices(self):\n",
    "        return len(self._outgoing)\n",
    "    def vertices(self):\n",
    "        return self._outgoing.keys()\n",
    "    @property\n",
    "    def n_edges(self):\n",
    "        total=sum(len(self._outgoing[v]) for v in self._outgoing)\n",
    "        return total if self.is_directed() else total // 2#无向图除2\n",
    "    def edges(self):\n",
    "        #返回所有的边\n",
    "        result=set()\n",
    "        for secondary_map in self._outgoing.values():#取键用keys取值用values\n",
    "            result.update(secondary_map.values())\n",
    "        return result\n",
    "    def get_edge(self,u,v):\n",
    "        #返回u-v的边\n",
    "        self._validate_vertex(u)\n",
    "        self._validate_vertex(v)\n",
    "        return self._outgoing[u].get(v)\n",
    "    def degree(self,v,outgoing=True):\n",
    "        self._validate_vertex(v)\n",
    "        adj = self._outgoing if outgoing else self._incoming\n",
    "        return len(adj[v])\n",
    "    def incident_edges(self, v, outgoing=True): \n",
    "        #返回所有和v邻接的边\n",
    "        self._validate_vertex(v)\n",
    "        adj = self._outgoing if outgoing else self. _incoming\n",
    "        for edge in adj[v].values():\n",
    "            yield edge\n",
    "    def insert_vertex(self, x=None): \n",
    "        #插入顶点\n",
    "        v = self.Vertex(x)\n",
    "        self._outgoing[v] = {}\n",
    "        if self.is_directed(): \n",
    "            self._incoming[v] = {} \n",
    "        return v\n",
    "    def insert_edge(self, u, v, x=None):\n",
    "        if self.get_edge(u, v) is not None:\n",
    "            raise ValueError('u and v are already adjacent')\n",
    "        e = self.Edge(u, v, x)\n",
    "        self._outgoing[u][v] = e\n",
    "        self._incoming[v][u] = e\n",
    "    def __repr__(self):\n",
    "        if self.is_directed():\n",
    "            return f'{self._outgoing}{self._incoming}'\n",
    "        else:\n",
    "            return f'{self._outgoing}'\n",
    "\n",
    "if __name__ =='__main__':\n",
    "    G=Graph()\n",
    "    print(G)\n",
    "    a=G.insert_vertex('a')\n",
    "    b=G.insert_vertex('b')\n",
    "    c=G.insert_vertex('c')\n",
    "    d=G.insert_vertex('d')\n",
    "    e=G.insert_vertex('e')\n",
    "    print(G)\n",
    "    \n",
    "    G.insert_edge(a,b)\n",
    "    G.insert_edge(a,c)\n",
    "    G.insert_edge(a,d)\n",
    "    G.insert_edge(a,e)\n",
    "    G.insert_edge(b,c)\n",
    "    G.insert_edge(c,d)\n",
    "    G.insert_edge(d,e)\n",
    "    \n",
    "    print(G)\n",
    "    print(G.n_vertices)\n",
    "    print(G.n_edges)\n",
    "    print(list(G.vertices()))\n",
    "    print(list(G.edges()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{a: None, b: (a,b), c: (b,c), d: (c,d), e: (d,e)}\n",
      "a path from a to d is [a, b, c, d]\n",
      "forest in G is {a: None, b: (a,b), c: (b,c), d: (c,d), e: (d,e), f: None, g: (f,g), i: (g,i), h: (f,h)}\n"
     ]
    }
   ],
   "source": [
    "def DFS(g, u, discovered):\n",
    "    for e in g.incident_edges(u):    # for every outgoing edge from u\n",
    "        v = e.opposite(u)\n",
    "        if v not in discovered:        # v is an unvisited vertex\n",
    "            discovered[v] = e            # e is the tree edge that discovered v\n",
    "            DFS(g, v, discovered)        # recursively explore from v\n",
    "\n",
    "def construct_path(u, v, discovered):\n",
    "    path = []\n",
    "    if v in discovered:\n",
    "        path.append(v)\n",
    "        walk=v\n",
    "        while walk is not u:\n",
    "            e=discovered[walk]\n",
    "            parent=e.opposite(walk)\n",
    "            path.append(parent)\n",
    "            walk=parent\n",
    "        path.reverse()\n",
    "    return path\n",
    "\n",
    "def DFS_complete(g):\n",
    "    forest={}\n",
    "    for u in g.vertices():\n",
    "        if u not in forest:\n",
    "            forest[u]=None\n",
    "            DFS(g,u,forest)\n",
    "    return forest\n",
    "\n",
    "if __name__ =='__main__':\n",
    "    G=Graph()\n",
    "    \n",
    "    a=G.insert_vertex('a')\n",
    "    b=G.insert_vertex('b')\n",
    "    c=G.insert_vertex('c')\n",
    "    d=G.insert_vertex('d')\n",
    "    e=G.insert_vertex('e')\n",
    "\n",
    "    G.insert_edge(a,b)\n",
    "    G.insert_edge(a,c)\n",
    "    G.insert_edge(a,d)\n",
    "    G.insert_edge(a,e)\n",
    "    G.insert_edge(b,c)\n",
    "    G.insert_edge(c,d)\n",
    "    G.insert_edge(d,e)\n",
    "    \n",
    "    f=G.insert_vertex('f')\n",
    "    g=G.insert_vertex('g')\n",
    "    h=G.insert_vertex('h')\n",
    "    i=G.insert_vertex('i')\n",
    "    \n",
    "    G.insert_edge(f,g)\n",
    "    G.insert_edge(f,h)\n",
    "    G.insert_edge(f,i)\n",
    "    G.insert_edge(g,i)\n",
    "    \n",
    "    bfs_tree={a:None}\n",
    "    DFS(G,a,bfs_tree)\n",
    "    print(bfs_tree)\n",
    "    \n",
    "    path=construct_path(a,d,bfs_tree)\n",
    "    print(f'a path from a to d is {path}')\n",
    "    \n",
    "    forest=DFS_complete(G)\n",
    "    print(f'forest in G is {forest}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
